// 第2次算法作业 习题1.4.15
package Exercises.chapter1;

public class e1_4_15 {
    public static int TwoSumFaster(int a[]){
        int N=a.length;
        int cnt=0;
        int p=0,q=N-1;
        while(p<q&&a[p]<0&&a[q]>0){
            if(a[p]+a[q]==0) cnt++;
            if(-a[p]>a[q]) p++;
            else q--;
        }
        return cnt;
    }

    public static int ThreeSumFaster(int a[]){
        int N=a.length;
        int cnt=0;
        int p=0,q=N-1,mid=p+1;
        for(p=0;p<q-1&&a[p]<0;p++){
            mid=p+1;
            q=N-1;
            while(mid<q&&a[q]>0){
                if(a[p]+a[mid]+a[q]==0) cnt++;
                if(-a[p]-a[mid]>a[q]) mid++;
                else q--;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        int a[]={-3,-2,-1,0,1,2,3};
        System.out.println(e1_4_15.TwoSumFaster(a));
        System.out.println(e1_4_15.ThreeSumFaster(a));
    }
}
